/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						 abstract_adventure_map.cpp

	$Header: /heroes4/abstract_adventure_map.cpp $

	$NoKeywords: $

 ************************************************************************/

#include "precompiled.h"
#include "precompiled.h"
#pragma warning( disable: 4786 ) // Disable the ever so helpful "identifier was truncated to '255' characters" warning

#include "abstract_adventure_map.h"

#include <algorithm>
#include <cassert>
#include <utility>

#include "abstract_adv_object.h"
#include "adv_object_model.h"
#include "difficulty_level.h"
#include "elements_of.h"
#include "external_string.h"
#include "footprint.h"
#include "pixel_24.h"

#include "static_vector.h"

// -------------------------------------------------------------------
// Unnamed namespace
// -------------------------------------------------------------------
namespace
{
	t_external_string const k_default_map_name( "default_map_name.misc" );

	// -------------------------------------------------------------------
	// t_object_info struct
	// -------------------------------------------------------------------

	struct t_object_info
	{
		// Data members
		int			height;
		unsigned	placement_num;

		// Constructor
		t_object_info();
	};

	inline t_object_info::t_object_info()
		:	height( 0 ),
			placement_num( 0 )
	{
	}

	// -------------------------------------------------------------------
	// t_object_info_array class
	// -------------------------------------------------------------------

	class t_object_info_array
	{
	public:
		// Types
		typedef t_abstract_adventure_map::t_object_id t_object_id;

		// Constructor
		t_object_info_array();

		// Member functions
		t_object_info & get( t_object_id id );
		t_object_info const & get( t_object_id id ) const;
		t_object_info const & get_const( t_object_id id ) const;
		t_object_id get_count() const;
		t_object_info & append_new();

		// Operators
		t_object_info & operator[]( t_object_id id );
		t_object_info const & operator[]( t_object_id id ) const;

	private:
		// Types
		typedef std::vector< t_object_info > t_obj_info_vector;
		class t_obj_info_vector_ptr : public t_copy_on_write_ptr< t_obj_info_vector > {};

		typedef std::vector< t_obj_info_vector_ptr > t_obj_info_vector_ptr_vector;
		class t_obj_info_vector_ptr_vector_ptr : public t_copy_on_write_ptr< t_obj_info_vector_ptr_vector > {};

		typedef std::vector< t_obj_info_vector_ptr_vector_ptr > t_obj_info_vector_ptr_vector_ptr_vector;
		class t_obj_info_vector_ptr_vector_ptr_vector_ptr : public t_copy_on_write_ptr< t_obj_info_vector_ptr_vector_ptr_vector > {};

		t_object_id									m_count;
		t_obj_info_vector_ptr_vector_ptr_vector_ptr	m_obj_info_vector_ptr_vector_ptr_vector_ptr;
	};

	inline t_object_info_array::t_object_info_array()
		:	m_count( 0 )
	{
	}

	t_object_info & t_object_info_array::get( t_object_id id )
	{
		t_obj_info_vector_ptr_vector_ptr & obj_info_vector_ptr_vector_ptr = ( *m_obj_info_vector_ptr_vector_ptr_vector_ptr )[ id >> 12 /*/ 4096*/ ];
		id &= 0xFFF /*% 4096*/;
		t_obj_info_vector_ptr & obj_info_vector_ptr = ( *obj_info_vector_ptr_vector_ptr )[ id >> 6 /*/ 64*/ ];
		id &= 0x3F /*% 64*/;
		return ( *obj_info_vector_ptr )[ id ];
	}

	t_object_info const & t_object_info_array::get( t_object_id id ) const
	{
		t_obj_info_vector_ptr_vector_ptr const & obj_info_vector_ptr_vector_ptr = ( *m_obj_info_vector_ptr_vector_ptr_vector_ptr )[ id >> 12 /*/ 4096*/ ];
		id &= 0xFFF /*% 4096*/;
		t_obj_info_vector_ptr const & obj_info_vector_ptr = ( *obj_info_vector_ptr_vector_ptr )[ id >> 6 /*/ 64*/ ];
		id &= 0x3F /*% 64*/;
		return ( *obj_info_vector_ptr )[ id ];
	}

	inline t_object_info const & t_object_info_array::get_const( t_object_id id ) const
	{
		return get( id );
	}

	inline t_object_info_array::t_object_id t_object_info_array::get_count() const
	{
		return m_count;
	}

	t_object_info & t_object_info_array::append_new()
	{
		t_obj_info_vector * obj_info_vector_ptr;

		t_obj_info_vector_ptr_vector_ptr_vector & obj_info_vector_ptr_vector_ptr_vector = *m_obj_info_vector_ptr_vector_ptr_vector_ptr;

		if ( ( m_count & 0xFFF ) != 0 )
		{
			t_obj_info_vector_ptr_vector & obj_info_vector_ptr_vector = *obj_info_vector_ptr_vector_ptr_vector.back();

			if ( ( m_count & 0x3F ) == 0 )
				obj_info_vector_ptr_vector.push_back( t_obj_info_vector_ptr() );

			obj_info_vector_ptr = obj_info_vector_ptr_vector.back().get();
		}
		else
		{
			obj_info_vector_ptr_vector_ptr_vector.push_back( t_obj_info_vector_ptr_vector_ptr() );
			t_obj_info_vector_ptr_vector & obj_info_vector_ptr_vector = *obj_info_vector_ptr_vector_ptr_vector.back();
			obj_info_vector_ptr_vector.push_back( t_obj_info_vector_ptr() );
			obj_info_vector_ptr = obj_info_vector_ptr_vector.back().get();
		}

		obj_info_vector_ptr->push_back( t_object_info() );
		++m_count;

		return obj_info_vector_ptr->back();
	}

	inline t_object_info & t_object_info_array::operator[]( t_object_id id )
	{
		return get( id );
	}

	inline t_object_info const & t_object_info_array::operator[]( t_object_id id ) const
	{
		return get( id );
	}

	// -------------------------------------------------------------------
	// Convert a t_screen_rect in pixel coordinates to view cell
	// coordinates
	// -------------------------------------------------------------------
	inline t_screen_rect to_view_cell_coordinates( t_screen_rect const & rect )
	{
		return t_screen_rect(
					rect.left >> k_adventure_map_view_cell_shift,
					rect.top >> k_adventure_map_view_cell_shift,
					( rect.right + k_adventure_map_view_cell_size - 1 ) >> k_adventure_map_view_cell_shift,
					( rect.bottom + k_adventure_map_view_cell_size - 1 ) >> k_adventure_map_view_cell_shift );
	}

	// -------------------------------------------------------------------
	// t_adventure_map_view_cell_grid class
	// -------------------------------------------------------------------

	class t_adventure_map_view_cell_grid
	{
	public:
		// Types
		typedef t_abstract_adventure_map::t_view_cell t_view_cell;

		// Constructor
		t_adventure_map_view_cell_grid();
		t_adventure_map_view_cell_grid( t_screen_rect const & extents );

		// Member functions
		t_view_cell &		get( t_screen_point const & point );
		t_view_cell const & get( t_screen_point const & point ) const;
		t_view_cell const & get_const( t_screen_point const & point ) const
		{ return get( point ); }
		bool				is_valid( t_screen_point const& point ) const;
		void				resize( t_screen_rect const & extents );

	private:
		// Static data
		enum { k_segment_size = 4 };

		// Types
		typedef t_static_vector< t_static_vector< t_view_cell, k_segment_size >, k_segment_size > t_segment;
		typedef t_copy_on_write_ptr< std::vector< t_copy_on_write_ptr< t_segment > > > t_segment_ptr_vector_ptr;

		// Data members
		t_screen_point				m_origin;
		int							m_segments_wide;
		t_segment_ptr_vector_ptr	m_segment_ptr_vector_ptr;
	};

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	inline t_adventure_map_view_cell_grid::t_adventure_map_view_cell_grid()
		:	m_origin( 0, 0 ),
			m_segments_wide( 0 )
	{
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	inline t_adventure_map_view_cell_grid::t_adventure_map_view_cell_grid( t_screen_rect const & extents )
	{
		resize( extents );
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	void t_adventure_map_view_cell_grid::resize( t_screen_rect const & extents )
	{
		assert( is_normalized( extents ) );

		m_origin = extents.top_left();
		m_segments_wide = ( extents.width() + k_segment_size - 1 ) / k_segment_size;
		int segments_high = ( extents.height() + k_segment_size - 1 ) / k_segment_size;
		m_segment_ptr_vector_ptr->resize( m_segments_wide * segments_high );
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	t_abstract_adventure_map::t_view_cell & t_adventure_map_view_cell_grid::get( t_screen_point const & point )
	{
		t_screen_point adj_point = point - m_origin;
		t_screen_point remainder;

		remainder.x = adj_point.x % k_segment_size;
		remainder.y = adj_point.y % k_segment_size;
		adj_point.x /= k_segment_size;
		adj_point.y /= k_segment_size;
		adj_point.y *= m_segments_wide;

		assert( adj_point.x >= 0 );
		assert( adj_point.y >= 0 );
		assert( adj_point.x < m_segments_wide );
		assert( adj_point.y < (int)m_segment_ptr_vector_ptr->size() );
		assert( remainder.y >= 0 );
		assert( remainder.x >= 0 );

		t_segment & segment = *( *m_segment_ptr_vector_ptr )[ adj_point.y + adj_point.x ];
		return segment[ remainder.y ][ remainder.x ];
	}

	inline
	bool t_adventure_map_view_cell_grid::is_valid( t_screen_point const& point ) const
	{
		t_screen_point adj_point = point - m_origin;

		if (adj_point.x < 0 || adj_point.y < 0)
			return false;

		adj_point.x /= k_segment_size;
		adj_point.y /= k_segment_size;
		adj_point.y *= m_segments_wide;
		return adj_point.x >= 0 && adj_point.y >= 0 && adj_point.x < m_segments_wide
 			&& adj_point.y < (int)m_segment_ptr_vector_ptr->size();
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	t_abstract_adventure_map::t_view_cell const & t_adventure_map_view_cell_grid::get( t_screen_point const & point ) const
	{
		t_screen_point adj_point = point - m_origin;
		assert( adj_point.x < m_segments_wide * k_segment_size );
		assert( adj_point.y < ( (int)m_segment_ptr_vector_ptr->size() / m_segments_wide ) * k_segment_size );

		t_segment const & segment = *( *m_segment_ptr_vector_ptr )[ adj_point.y / k_segment_size * m_segments_wide + adj_point.x / k_segment_size ];
		return segment[ adj_point.y % k_segment_size ][ adj_point.x % k_segment_size ];
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	int compute_vertex_light_helper( int left_height, int center_height, int right_height )
	{
		return ( compute_edge_light( left_height, center_height ) + compute_edge_light( center_height, right_height ) ) / 2;
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	template < typename t_test_visibility >
	bool is_under_fog_of_war_helper(
		t_abstract_adventure_map const &	map,
		int									team_num,
		t_level_map_point_2d const &		object_pos,
		t_map_point_2d const &				footprint_size,
		t_test_visibility					test_visibility )
	{
		assert( team_num >= 0 );

		// An object is considered visible if any of its footprint cells are visible
		int begin_row = 0;
		if ( object_pos.row > begin_row )
			begin_row = object_pos.row;

		int end_row = map.get_size();
		if ( object_pos.row + footprint_size.row < end_row )
			end_row = object_pos.row + footprint_size.row;

		t_map_point_2d tile_point;
		for (	tile_point.row = begin_row;
				tile_point.row < end_row;
				++tile_point.row )
		{
			int begin_col = map.get_row_start( tile_point.row );
			if ( object_pos.column > begin_col )
				begin_col = object_pos.column;

			int end_col = map.get_row_end( tile_point.row );
			if ( object_pos.column + footprint_size.column < end_col )
				end_col = object_pos.column + footprint_size.column;

			for (	tile_point.column = begin_col;
					tile_point.column < end_col;
					++tile_point.column )
			{
				t_abstract_adventure_map::t_tile const & tile =
					map.get_tile( t_level_map_point_2d( tile_point, object_pos.level ) );
				if ( test_visibility( tile.get_visibility( team_num ) ) )
					return false;
			}
		}

		return true;
	}

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	struct t_test_visible
	{
		bool operator()( t_tile_visibility visibility ) const
		{
			return visibility == k_tile_visible;
		}
	};

	// -------------------------------------------------------------------
	// -------------------------------------------------------------------
	struct t_test_explored
	{
		bool operator()( t_tile_visibility visibility ) const
		{
			return visibility != k_tile_never_explored;
		}
	};

} // Unnamed namespace

// -------------------------------------------------------------------
// t_abstract_adventure_tile members
// -------------------------------------------------------------------

// -------------------------------------------------------------------
// -------------------------------------------------------------------
void t_abstract_adventure_tile::add_intersecting_object_id( t_object_id object_id )
{
	t_object_id_vector & object_id_vector = *m_object_id_vector_ptr;

	t_object_id_vector::iterator insert_iter =
		std::lower_bound(
			object_id_vector.begin(),
			object_id_vector.end(),
			object_id );
	assert( insert_iter == object_id_vector.end() || *insert_iter != object_id );

	object_id_vector.insert( insert_iter, object_id );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
void t_abstract_adventure_tile::remove_intersecting_object_id( t_object_id object_id )
{
	t_object_id_vector & object_id_vector = *m_object_id_vector_ptr;

	t_object_id_vector::iterator erase_iter =
		std::lower_bound(
			object_id_vector.begin(),
			object_id_vector.end(),
			object_id );
	assert( erase_iter != object_id_vector.end() && *erase_iter == object_id );

	object_id_vector.erase( erase_iter );
}

// -------------------------------------------------------------------
// t_adventure_map_view_cell members
// -------------------------------------------------------------------

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_adventure_map_view_cell::t_const_shadow_object_id_iterator
t_adventure_map_view_cell::shadow_insert( t_object_id new_shadow_object_id )
{
	t_shadow_object_id_vector const & const_vector = *m_shadow_object_id_vector_ptr.get_const();

	t_shadow_object_id_vector::const_iterator const_iter =
		std::lower_bound(
			const_vector.begin(),
			const_vector.end(),
			new_shadow_object_id );

	if ( const_iter == const_vector.end() || *const_iter != new_shadow_object_id )
	{
		t_shadow_object_id_vector::size_type index = const_iter - const_vector.begin();
		t_shadow_object_id_vector & vector = *m_shadow_object_id_vector_ptr;
		const_iter = vector.insert( vector.begin() + index, new_shadow_object_id );
	}

	return const_iter;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
void t_adventure_map_view_cell::shadow_erase( t_object_id shadow_object_id )
{
	t_shadow_object_id_vector const & const_vector = *m_shadow_object_id_vector_ptr.get_const();

	t_shadow_object_id_vector::const_iterator const_iter =
		std::lower_bound(
			const_vector.begin(),
			const_vector.end(),
			shadow_object_id );

	if ( const_iter != const_vector.end() && *const_iter == shadow_object_id )
	{
		t_shadow_object_id_vector::size_type index = const_iter - const_vector.begin();
		t_shadow_object_id_vector & vector = *m_shadow_object_id_vector_ptr;
		vector.erase( vector.begin() + index );
	}
}

// -------------------------------------------------------------------
// t_abstract_adventure_map::t_impl class
// -------------------------------------------------------------------

class t_abstract_adventure_map::t_impl
{
public:
	// Types
	struct t_properties
	{
		struct t_row_info
		{
			int						start;
			int						end;
		};

		int							size;
		int							levels;
		t_screen_point				view_size;
		std::vector< t_row_info >	row_vector;
		std::vector< t_row_info >	vertex_row_vector;
		long						terrain_random_seed;
		std::string					map_name;
		std::string					map_description;
		t_difficulty                map_difficulty;
	};

	typedef t_adventure_map_view_cell_grid		t_view_cell_grid;

	// Data members
	unsigned												num_object_placements;
	t_copy_on_write_ptr< t_properties >						properties_ptr;
	t_copy_on_write_ptr< std::vector< t_view_cell_grid > >	view_cell_grid_vector_ptr;
	t_object_info_array										object_info_array;

	// Member functions
	t_view_cell_grid & get_view_cell_grid( int level );
	t_view_cell_grid const & get_view_cell_grid( int level ) const;
	t_view_cell_grid const & get_const_view_cell_grid( int level ) const { return get_view_cell_grid( level ); }
};

// -------------------------------------------------------------------
// -------------------------------------------------------------------
inline t_adventure_map_view_cell_grid & t_abstract_adventure_map::t_impl::get_view_cell_grid( int level )
{
	return ( *view_cell_grid_vector_ptr )[ level ];
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
inline t_adventure_map_view_cell_grid const & t_abstract_adventure_map::t_impl::get_view_cell_grid( int level ) const
{
	return ( *view_cell_grid_vector_ptr )[ level ];
}

// -------------------------------------------------------------------
// t_abstract_adventure_map members
// -------------------------------------------------------------------

// -------------------------------------------------------------------
// Constructor
// -------------------------------------------------------------------
t_abstract_adventure_map::t_abstract_adventure_map()
{
}

// -------------------------------------------------------------------
// Copy constructor
// -------------------------------------------------------------------
t_abstract_adventure_map::t_abstract_adventure_map( t_abstract_adventure_map const & other )
	:	m_impl_ptr( other.m_impl_ptr )
{
}

// -------------------------------------------------------------------
// Constructor
// -------------------------------------------------------------------
t_abstract_adventure_map::t_abstract_adventure_map( t_params const & params )
{
	init( params );
}

// -------------------------------------------------------------------
// Constructor
// -------------------------------------------------------------------
t_abstract_adventure_map::t_abstract_adventure_map( int size, int levels, long terrain_random_seed )
{
	t_params params;
	params.size = size;
	params.levels = levels;
	params.terrain_random_seed = terrain_random_seed;

	init( params );
}

// -------------------------------------------------------------------
// Constructor helper
// -------------------------------------------------------------------
void t_abstract_adventure_map::init( t_params const & params )
{
	t_impl & impl = *m_impl_ptr;
	t_impl::t_properties & properties = *impl.properties_ptr;

	properties.size = params.size;
	properties.levels = params.levels;
	properties.view_size.x = k_adventure_tile_width * properties.size / 2;
	properties.view_size.y = k_adventure_tile_height * properties.size / 2;
	properties.terrain_random_seed = params.terrain_random_seed;
	properties.map_name = k_default_map_name;
	properties.map_difficulty = k_difficulty_normal;

	impl.num_object_placements = 0;

	{
		// initialize row start, row end variables.  Create an isometric map to do the computation.
		t_isometric_map< unsigned char > temp_map( properties.size, 1, k_adventure_tile_height );

		properties.row_vector.resize( properties.size );
		int row;
		for ( row = 0; row < properties.size; ++row )
		{
			properties.row_vector[ row ].start = temp_map.get_row_start( row );
			properties.row_vector[ row ].end = temp_map.get_row_end( row );
		}
	}

	{
		t_isometric_vertex_map< unsigned char > temp_map( properties.size, 1, k_adventure_tile_height );

		properties.vertex_row_vector.resize( properties.size + 1 );
		int row;
		for ( row = 0; row <= properties.size; ++row )
		{
			properties.vertex_row_vector[ row ].start = temp_map.get_row_start( row );
			properties.vertex_row_vector[ row ].end = temp_map.get_row_end( row );
		}
	}

	// Initialize the view cell maps
	t_screen_point view_size = get_view_size();
	t_screen_rect	view_cell_grid_extents(
						0,
						-( ( k_max_tile_vertex_height + k_view_cell_size - 1 ) / k_view_cell_size ),
						( view_size.x + k_view_cell_size - 1 ) / k_view_cell_size,
						( view_size.y + k_view_cell_size - 1 ) / k_view_cell_size );

	impl.view_cell_grid_vector_ptr->resize( get_num_levels(), t_impl::t_view_cell_grid( view_cell_grid_extents ) );
}

// -------------------------------------------------------------------
// Destructor
// -------------------------------------------------------------------
t_abstract_adventure_map::~t_abstract_adventure_map()
{
}

// -------------------------------------------------------------------
// Copy assignment operator
// -------------------------------------------------------------------
t_abstract_adventure_map & t_abstract_adventure_map::operator=( t_abstract_adventure_map const & other )
{
	m_impl_ptr = other.m_impl_ptr;
	return *this;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_abstract_adventure_map::t_apply_height_map_result
t_abstract_adventure_map::apply_height_map( int level, t_height_map const & height_map )
{
	assert( level >= 0 && level < get_num_levels() );

	typedef t_vector_set< t_object_id > t_object_id_set;

	t_apply_height_map_result result;

	t_tile_point_set & modified_vertex_points = result.modified_vertex_points;
	t_object_height_delta_set & modified_object_height_deltas = result.modified_object_height_deltas;

	t_object_id_set potentially_affected_object_ids;

	// Run through all of the vertices in the height map
	t_height_map::const_iterator height_map_iter = height_map.begin();
	for ( ; height_map_iter != height_map.end(); ++height_map_iter )
	{
		t_map_point_2d const & vertex_point = height_map_iter->first;
		assert( is_vertex_valid( height_map_iter->first ) );

		// Set the vertex height
		int new_vertex_height = height_map_iter->second;
		get_tile_vertex( t_level_map_point_2d( vertex_point, level ) ).set_height( new_vertex_height );

		// Record which vertices are affected
		modified_vertex_points.insert( vertex_point );

		if ( vertex_point.column > get_vertex_row_start( vertex_point.row ) )
			modified_vertex_points.insert( vertex_point - t_map_point_2d( 0, 1 ) );

		if ( vertex_point.column < get_vertex_row_end( vertex_point.row ) - 1 )
			modified_vertex_points.insert( vertex_point + t_map_point_2d( 0, 1 ) );

		// Record the ids of the objects in the adjacent tiles
		static t_map_point_2d const k_adj_tile_point_offset_array[] =
		{
			t_map_point_2d( -1, -1 ),
			t_map_point_2d( -1, 0 ),
			t_map_point_2d( 0, -1 ),
			t_map_point_2d( 0, 0 ),
		};

		int i;
		for ( i = 0; i < ELEMENTS_OF( k_adj_tile_point_offset_array ); ++i )
		{
			t_map_point_2d adj_tile_point = vertex_point + k_adj_tile_point_offset_array[ i ];
			if ( !is_valid( adj_tile_point ) )
				continue;

			t_tile const & adj_tile = get_tile( t_level_map_point_2d( adj_tile_point, level ) );
			int intersecting_object_count = adj_tile.get_intersecting_object_count();
			int intersecting_object_num;
			for ( intersecting_object_num = 0; intersecting_object_num < intersecting_object_count; ++intersecting_object_num )
				potentially_affected_object_ids.insert( adj_tile.get_intersecting_object_id( intersecting_object_num ) );
		}
	}

	// Fixup the lighting on all of the affected vertices
	t_tile_point_set::iterator affected_vertex_iter = modified_vertex_points.begin();
	while ( affected_vertex_iter != modified_vertex_points.end() )
	{
		t_map_point_2d vertex_point = *affected_vertex_iter;
		assert( is_vertex_valid( vertex_point ) );

		// Get this vertex
		t_tile_vertex const & const_tile_vertex = get_const_tile_vertex( t_level_map_point_2d( vertex_point, level ) );

		// Compute the new lighting for this vertex
		int new_light = compute_vertex_light( t_level_map_point_2d( vertex_point, level ) );

		// If the new light is different than the current light, set the new light
		if ( new_light != const_tile_vertex.get_light() )
		{
			get_tile_vertex( t_level_map_point_2d( vertex_point, level ) ).set_light( new_light );
			++affected_vertex_iter;
		}
		else if ( height_map.find( vertex_point ) == height_map.end() )
			affected_vertex_iter = modified_vertex_points.erase( affected_vertex_iter );
		else
			++affected_vertex_iter;
	}

	// Now run through all of the potentially affected objects and if necessary set their new heights
	t_impl & impl = *m_impl_ptr;
	t_object_id_set::const_iterator object_id_iter = potentially_affected_object_ids.begin();
	for ( ; object_id_iter != potentially_affected_object_ids.end(); ++object_id_iter )
	{
		t_object const & object = get_const_object( *object_id_iter );
		t_level_map_point_2d object_pos = get_object_pos( *object_id_iter );

		int current_height = get_object_height( *object_id_iter );
		int new_height = compute_height( object, object_pos );

		if ( new_height != current_height )
		{
			unstamp_object_image( *object_id_iter );
			impl.object_info_array[ *object_id_iter ].height = new_height;
			stamp_object_image( *object_id_iter );

			modified_object_height_deltas.insert( std::make_pair( *object_id_iter, new_height - current_height ) );
		}
	}

	return result;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
void t_abstract_adventure_map::apply_height_map( t_isometric_vertex_map< int > const & height_map )
{
	int levels = get_num_levels();
	int size = get_size();

	assert( height_map.get_levels() == levels );
	assert( height_map.get_size() == size + 1 );

	// Run through all of the tile vertices setting the height
	t_level_map_point_2d vertex_point;
	for ( vertex_point.level = 0; vertex_point.level < levels; ++vertex_point.level )
	{
		for ( vertex_point.row = 0; vertex_point.row < size + 1; ++vertex_point.row )
		{
			int row_start = get_vertex_row_start( vertex_point.row );
			int row_end = get_vertex_row_end( vertex_point.row );
			for ( vertex_point.column = row_start; vertex_point.column < row_end; ++vertex_point.column )
			{
				assert( height_map.is_valid( vertex_point ) );
				get_tile_vertex( vertex_point ).set_height( height_map.get( vertex_point ) );
			}
		}
	}

	// Fixup the lighting for all the tile vertices
	for ( vertex_point.level = 0; vertex_point.level < levels; ++vertex_point.level )
	{
		for ( vertex_point.row = 0; vertex_point.row < size + 1; ++vertex_point.row )
		{
			int row_start = get_vertex_row_start( vertex_point.row );
			int row_end = get_vertex_row_end( vertex_point.row );
			for ( vertex_point.column = row_start; vertex_point.column < row_end; ++vertex_point.column )
				get_tile_vertex( vertex_point ).set_light( compute_vertex_light( vertex_point ) );
		}
	}

	// Adjust the heights the adventure objects on the map
	t_impl & impl = *m_impl_ptr;
	t_object_id object_id;
	for ( object_id = get_first_object_id(); object_id != k_invalid_object_id; object_id = get_next_object_id( object_id ) )
	{
		if ( is_floating( object_id ) )
			continue;

		t_object const & object = get_const_object( object_id );
		t_level_map_point_2d object_pos = get_object_pos( object_id );

		int current_height = get_object_height( object_id );
		int new_height = compute_height( object, object_pos );

		if ( new_height != current_height )
		{
			unstamp_object_image( object_id );
			impl.object_info_array[ object_id ].height = new_height;
			stamp_object_image( object_id );
		}
	}
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_size() const
{
	return m_impl_ptr->properties_ptr->size;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_num_levels() const
{
	return m_impl_ptr->properties_ptr->levels;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_object_height( t_object_id id ) const
{
	t_impl const & impl = *m_impl_ptr;
	assert( id >= 0 && id < impl.object_info_array.get_count() );
	return impl.object_info_array[ id ].height;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_row_start( int row ) const
{
	assert( row >= 0 && row < get_size() );
	return m_impl_ptr->properties_ptr->row_vector[ row ].start;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_row_end( int row ) const
{
	assert( row >= 0 && row < get_size() );
	return m_impl_ptr->properties_ptr->row_vector[ row ].end;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
long t_abstract_adventure_map::get_terrain_random_seed() const
{
	return m_impl_ptr->properties_ptr->terrain_random_seed;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_abstract_adventure_map::t_const_tile_vertex_quad
t_abstract_adventure_map::get_tile_vertex_quad( t_level_map_point_2d point ) const
{
	t_tile_vertex const & left =
		get_tile_vertex(
			t_level_map_point_2d( point.row + 1, point.column, point.level ) );

	t_tile_vertex const & top = get_tile_vertex( point );

	t_tile_vertex const & right =
		get_tile_vertex(
			t_level_map_point_2d( point.row, point.column + 1, point.level ) );

	t_tile_vertex const & bottom =
		get_tile_vertex(
			t_level_map_point_2d( point.row + 1, point.column + 1, point.level ) );

	return t_const_tile_vertex_quad( left, top, right, bottom );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_abstract_adventure_map::t_tile_vertex_quad
t_abstract_adventure_map::get_tile_vertex_quad( t_level_map_point_2d point )
{
	t_tile_vertex & left =
		get_tile_vertex(
			t_level_map_point_2d( point.row + 1, point.column, point.level ) );

	t_tile_vertex & top = get_tile_vertex( point );

	t_tile_vertex & right =
		get_tile_vertex(
			t_level_map_point_2d( point.row, point.column + 1, point.level ) );

	t_tile_vertex & bottom =
		get_tile_vertex(
			t_level_map_point_2d( point.row + 1, point.column + 1, point.level ) );

	return t_tile_vertex_quad( left, top, right, bottom );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_vertex_row_start( int row ) const
{
	assert( row >= 0 && row <= get_size() );
	return m_impl_ptr->properties_ptr->vertex_row_vector[ row ].start;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::get_vertex_row_end( int row ) const
{
	assert( row >= 0 && row <= get_size() );
	return m_impl_ptr->properties_ptr->vertex_row_vector[ row ].end;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_screen_point t_abstract_adventure_map::get_view_size() const
{
	return m_impl_ptr->properties_ptr->view_size;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool t_abstract_adventure_map::is_valid( t_map_point_2d const & point ) const
{
	return		point.row >= 0
			&&	point.row < get_size()
			&&	point.column >= get_row_start( point.row )
			&&	point.column < get_row_end( point.row );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool t_abstract_adventure_map::is_valid( t_level_map_point_2d const & point ) const
{
	return		point.level >= 0
			&&	point.level < get_num_levels()
			&&	is_valid( static_cast< t_map_point_2d const & >( point ) );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool t_abstract_adventure_map::is_vertex_valid( t_map_point_2d const & point ) const
{
	return		point.row >= 0
			&&	point.row <= get_size()
			&&	point.column >= get_vertex_row_start( point.row )
			&&	point.column < get_vertex_row_end( point.row );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool t_abstract_adventure_map::is_vertex_valid( t_level_map_point_2d const & point ) const
{
	return		point.level >= 0
			&&	point.level < get_num_levels()
			&&	is_vertex_valid( static_cast< t_map_point_2d const & >( point ) );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_map_point_2d t_abstract_adventure_map::get_map_point( t_screen_point point ) const
{
	return convert_screen_point_to_map( point, k_adventure_tile_height, get_view_size(), get_size() );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_screen_point t_abstract_adventure_map::get_screen_point( t_map_point_2d point ) const
{
	return convert_map_point_to_screen( point, k_adventure_tile_height, get_view_size(), get_size() );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_abstract_adventure_map::t_view_cell const & 
t_abstract_adventure_map::get_view_cell( int level, t_screen_point cell_point ) const
{
	assert( level >= 0 && level < get_num_levels() );
	return m_impl_ptr->get_view_cell_grid( level ).get( cell_point );
}

bool t_abstract_adventure_map::is_valid_view_cell( int level, t_screen_point const& point ) const
{
	assert( level >= 0 && level < get_num_levels() );
	return m_impl_ptr->get_view_cell_grid( level ).is_valid( point );
}

// -------------------------------------------------------------------
// Stamp down the specified object's information in the intersecting
// view cells
// -------------------------------------------------------------------

void t_abstract_adventure_map::stamp_object( t_object_id id )
{
	// Get the object and its position
	t_object const & object = get_const_object( id );
	t_level_map_point_2d object_pos = get_object_pos( id );

	// Stamp down this object in all of the tiles which its footprint intersects
	t_map_point_2d footprint_size = object.get_footprint().get_size();
	t_map_point_2d tile_point;
	for (	tile_point.column = object_pos.column;
			tile_point.column < object_pos.column + footprint_size.column;
			++tile_point.column )
	{
		for (	tile_point.row = object_pos.row;
				tile_point.row < object_pos.row + footprint_size.row;
				++tile_point.row )
		{
			if ( !is_valid( tile_point ) )
				continue;

			t_tile & tile = get_tile( t_level_map_point_2d( tile_point, object_pos.level ) );
			tile.add_intersecting_object_id( id );
		}
	}

	stamp_object_image( id );
}

// -------------------------------------------------------------------
// Remove the specified object's information from the intersecting
// view cells
// -------------------------------------------------------------------

void t_abstract_adventure_map::unstamp_object( t_object_id id )
{
	unstamp_object_image( id );

	// Get the object and its position
	t_object const & object = get_const_object( id );
	t_level_map_point_2d object_pos = get_object_pos( id );

	// Un-stamp this object from all of the tiles which its footprint intersects
	t_map_point_2d footprint_size = object.get_footprint().get_size();
	t_map_point_2d tile_point;
	for (	tile_point.column = object_pos.column;
			tile_point.column < object_pos.column + footprint_size.column;
			++tile_point.column )
	{
		for (	tile_point.row = object_pos.row;
				tile_point.row < object_pos.row + footprint_size.row;
				++tile_point.row )
		{
			if ( !is_valid( tile_point ) )
				continue;

			t_tile & tile = get_tile( t_level_map_point_2d( tile_point, object_pos.level ) );
			tile.remove_intersecting_object_id( id );
		}
	}
}

// -------------------------------------------------------------------
// To be called when an object is floated
// -------------------------------------------------------------------
void t_abstract_adventure_map::on_floating_object( t_object_id id )
{
	on_removing_object( id );
}

// -------------------------------------------------------------------
// To be called just before an object is moved
// -------------------------------------------------------------------
void t_abstract_adventure_map::on_moving_object( t_object_id id )
{
	if ( !is_floating( id ) )
		on_removing_object( id );
}

// -------------------------------------------------------------------
// To be called just after an object is moved
// -------------------------------------------------------------------
void t_abstract_adventure_map::on_object_moved( t_object_id id )
{
	if ( !is_floating( id ) )
		on_object_placed( id );
}

// -------------------------------------------------------------------
// To be called just after an object is placed
// -------------------------------------------------------------------
void t_abstract_adventure_map::on_object_placed( t_object_id id )
{
	assert( id >= 0 && id <= m_impl_ptr.get_const()->object_info_array.get_count() );

	t_object const & object = get_const_object( id );
	t_level_map_point_2d object_pos = get_object_pos( id );

	t_impl & impl = *m_impl_ptr;
	
	t_object_info * new_object_info_ptr;
	if ( id >= m_impl_ptr.get_const()->object_info_array.get_count() )
		new_object_info_ptr = &impl.object_info_array.append_new();
	else
		new_object_info_ptr = &impl.object_info_array[ id ];
	new_object_info_ptr->height = compute_height( object, object_pos );
	new_object_info_ptr->placement_num = impl.num_object_placements++;

	stamp_object( id );
}

// -------------------------------------------------------------------
// To be called just after an object is sunk
// -------------------------------------------------------------------
void t_abstract_adventure_map::on_object_sunk( t_object_id id )
{
	on_object_placed( id );
}

// -------------------------------------------------------------------
// To be called just before an object is removed
// -------------------------------------------------------------------
void t_abstract_adventure_map::on_removing_object( t_object_id id )
{
	unstamp_object( id );
}

// -------------------------------------------------------------------
// Compute an object's visible extent relative the entire map's view
// area
// -------------------------------------------------------------------
t_screen_rect t_abstract_adventure_map::compute_object_extent( t_object_id id ) const
{
	t_screen_point obj_screen_point = get_screen_point( get_object_pos( id ) );
	obj_screen_point.y -= get_object_height( id );
	t_screen_point view_size = get_view_size();
	return	intersection(
				get_object( id ).get_rect() + obj_screen_point,
				t_screen_rect( 0, -k_max_tile_vertex_height, view_size.x, view_size.y ) );
}

// -------------------------------------------------------------------
// Compute an object shadow's visible extent relative the entire map's
// view area
// -------------------------------------------------------------------
t_screen_rect t_abstract_adventure_map::compute_object_shadow_extent( t_object_id id ) const
{
	t_screen_point obj_screen_point = get_screen_point( get_object_pos( id ) );
	obj_screen_point.y -= get_object_height( id );
	t_screen_point view_size = get_view_size();
	return	intersection(
				get_object( id ).get_shadow_rect() + obj_screen_point,
				t_screen_rect( 0, -k_max_tile_vertex_height, view_size.x, view_size.y ) );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
int t_abstract_adventure_map::compute_vertex_light( t_level_map_point_2d const & vertex_point ) const
{
	assert( is_vertex_valid( vertex_point ) );

	t_tile_vertex const & tile_vertex = get_tile_vertex( vertex_point );

	if ( vertex_point.column > get_vertex_row_start( vertex_point.row ) )
	{
		int left_height = get_tile_vertex( vertex_point + t_map_point_2d( 0, -1 ) ).get_height();
		if ( vertex_point.column < get_vertex_row_end( vertex_point.row ) - 1 )
		{
			int right_height = get_tile_vertex( vertex_point + t_map_point_2d( 0, 1 ) ).get_height();
			return compute_vertex_light_helper( left_height, tile_vertex.get_height(), right_height );
		}

		return compute_edge_light( left_height, tile_vertex.get_height() );
	}

	assert( vertex_point.column < get_vertex_row_end( vertex_point.row ) - 1 );
	int right_height = get_tile_vertex( vertex_point + t_map_point_2d( 0, 1 ) ).get_height();
	return compute_edge_light( tile_vertex.get_height(), right_height );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
unsigned t_abstract_adventure_map::get_object_placement_num( t_object_id id ) const
{
	t_impl const & impl = *m_impl_ptr;
	assert( id >= 0 && id < impl.object_info_array.get_count() );
	return impl.object_info_array[ id ].placement_num;
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
t_abstract_adventure_map::t_view_cell & t_abstract_adventure_map::get_view_cell( int level, t_screen_point cell_point )
{
	assert( level >= 0 && level < get_num_levels() );
	return m_impl_ptr->get_view_cell_grid( level ).get( cell_point );
}

// -------------------------------------------------------------------
// Get a long text description of the map, as entered by the map designer
// -------------------------------------------------------------------
std::string const & t_abstract_adventure_map::get_map_description() const
{
	return m_impl_ptr->properties_ptr->map_description;
}

// -------------------------------------------------------------------
// Get the map maker's idea of how hard the MAP is. This is the value
// entered in the map editor, not the difficulty level the player
// is playing at
// -------------------------------------------------------------------
t_difficulty t_abstract_adventure_map::get_map_difficulty() const
{
	return m_impl_ptr->properties_ptr->map_difficulty;
}

// -------------------------------------------------------------------
// The name of the map
// -------------------------------------------------------------------
std::string const & t_abstract_adventure_map::get_map_name() const
{
	return m_impl_ptr->properties_ptr->map_name;
}

// -------------------------------------------------------------------
// Set a long text description of the map
// -------------------------------------------------------------------
void t_abstract_adventure_map::set_map_description( std::string const & description )
{
	m_impl_ptr->properties_ptr->map_description = description;
}

// -------------------------------------------------------------------
// Set the map maker's idea of how hard the MAP is. 
// (Not the difficulty level the player is playing at)
// -------------------------------------------------------------------
void t_abstract_adventure_map::set_map_difficulty( t_difficulty difficulty )
{
	m_impl_ptr->properties_ptr->map_difficulty = difficulty;
}

// -------------------------------------------------------------------
// Set the name of the map
// -------------------------------------------------------------------
void t_abstract_adventure_map::set_map_name( std::string const & name )
{
	m_impl_ptr->properties_ptr->map_name = name;
}


// -------------------------------------------------------------------
// Stamp down the specified object's information in the intersecting
// view cells
// -------------------------------------------------------------------

void t_abstract_adventure_map::stamp_object_image( t_object_id id )
{
	t_screen_point view_size = get_view_size();

	// Get the object and its position
	t_object const & object = get_const_object( id );
	t_level_map_point_2d object_pos = get_object_pos( id );
	unsigned object_placement_num = get_object_placement_num( id );

	t_screen_point obj_screen_point = get_screen_point( object_pos );
	obj_screen_point.y -= get_object_height( id );

	// Compute this object's base depth
	int base_depth = -( object_pos.row + object_pos.column );

	// Get the extent of the object's shadow in view cell coordinates
	t_screen_rect shadow_extent = to_view_cell_coordinates( compute_object_shadow_extent( id ) );

	// Stamp down this object's shadow in all of the view cells it overlaps
	t_screen_point cell_point;
	for (	cell_point.y = shadow_extent.top;
			cell_point.y < shadow_extent.bottom;
			++cell_point.y )
	{
		for (	cell_point.x = shadow_extent.left;
				cell_point.x < shadow_extent.right;
				++cell_point.x )
			get_view_cell( object_pos.level, cell_point ).shadow_insert( id );
	}

	// Stamp down each of this object's subimages
	int subimage_num = object.get_subimage_count();
	while ( subimage_num > 0 )
	{
		--subimage_num;

		int subimage_depth = base_depth + object.get_subimage_depth_offset( subimage_num );
		bool subimage_is_underlay = object.subimage_is_underlay( subimage_num );

		// Get the extent of this subimage in view cell coordinates
		t_screen_rect subimage_extent =
			to_view_cell_coordinates(
				intersection(
					object.get_subimage_rect( subimage_num ) + obj_screen_point,
					t_screen_rect( 0, -k_max_tile_vertex_height, view_size.x, view_size.y ) ) );

		for (	cell_point.y = subimage_extent.top;
				cell_point.y < subimage_extent.bottom;
				++cell_point.y )
		{
			for (	cell_point.x = subimage_extent.left;
					cell_point.x < subimage_extent.right;
					++cell_point.x )
			{
				t_view_cell & view_cell = get_view_cell( object_pos.level, cell_point );
				t_view_cell::t_object_subimage_info_iterator subimage_info_iter =
					view_cell.object_subimage_end();

				if ( subimage_is_underlay )
				{
					// Underlays go under all non-underlays
					while ( subimage_info_iter != view_cell.object_subimage_begin() )
					{
						t_object_id other_object_id = ( subimage_info_iter - 1 )->object_id;
						int other_subimage_num = ( subimage_info_iter - 1 )->subimage_num;

						// If the next object subimage is an underlay then we've passed all of the non-underlays
						if ( get_const_object( other_object_id ).subimage_is_underlay( other_subimage_num ) )
							break;

						--subimage_info_iter;
					}
				}
				else
				{
					while ( subimage_info_iter != view_cell.object_subimage_begin() )
					{
						t_object_id other_object_id = ( subimage_info_iter - 1 )->object_id;
						int other_subimage_num = ( subimage_info_iter - 1 )->subimage_num;
						t_object const & other_object = get_const_object( other_object_id );

						// If the next object subimage is an underlay then we've passed all of the non-underlays
						if ( other_object.subimage_is_underlay( other_subimage_num ) )
							break;

						// Compare the depths of the subimages
						t_map_point_2d other_object_pos = get_object_pos( other_object_id );
						int other_subimage_depth =
								-( other_object_pos.row + other_object_pos.column )
							+	other_object.get_subimage_depth_offset( other_subimage_num );

						if (	subimage_depth < other_subimage_depth
							||	(	subimage_depth == other_subimage_depth
								&&	object_placement_num > get_object_placement_num( other_object_id ) ) )
							break;

						--subimage_info_iter;
					}
				}
				view_cell.object_subimage_insert(
					subimage_info_iter,
					t_view_cell::t_object_subimage_info( id, subimage_num ) );
			}
		}
	}
}

// -------------------------------------------------------------------
// Remove the specified object's information from the intersecting
// view cells
// -------------------------------------------------------------------

void t_abstract_adventure_map::unstamp_object_image( t_object_id id )
{
	t_screen_point view_size = get_view_size();

	// Get the object and its position
	t_object const & object = get_const_object( id );
	t_level_map_point_2d object_pos = get_object_pos( id );

	t_screen_point obj_screen_point = get_screen_point( object_pos );
	obj_screen_point.y -= get_object_height( id );

	// Un-stamp all of this object's subimages
	int subimage_num = object.get_subimage_count();
	while ( subimage_num > 0 )
	{
		--subimage_num;

		// Get the extent of this subimage in view cell coordinates
		t_screen_rect subimage_extent =
			to_view_cell_coordinates(
				intersection(
					object.get_subimage_rect( subimage_num ) + obj_screen_point,
					t_screen_rect( 0, -k_max_tile_vertex_height, view_size.x, view_size.y ) ) );

		t_screen_point cell_point;
		for (	cell_point.y = subimage_extent.top;
				cell_point.y < subimage_extent.bottom;
				++cell_point.y )
		{
			for (	cell_point.x = subimage_extent.left;
					cell_point.x < subimage_extent.right;
					++cell_point.x )
			{
				t_view_cell & view_cell = get_view_cell( object_pos.level, cell_point );
				t_view_cell::t_object_subimage_info_iterator subimage_info_iter =
					view_cell.object_subimage_begin();
				for (;;)
				{
					assert( subimage_info_iter != view_cell.object_subimage_end() );
					
					if (	subimage_info_iter->object_id == id
						&&	subimage_info_iter->subimage_num == subimage_num )
						break;

					++subimage_info_iter;
				}
				view_cell.object_subimage_erase( subimage_info_iter );
			}
		}
	}

	// Un-stamp this object's shadow
	// Get the object's extent in view cell coordinates
	t_screen_rect shadow_extent = to_view_cell_coordinates( compute_object_shadow_extent( id ) );

	t_screen_point cell_point;
	for (	cell_point.y = shadow_extent.top;
			cell_point.y < shadow_extent.bottom;
			++cell_point.y )
	{
		for (	cell_point.x = shadow_extent.left;
				cell_point.x < shadow_extent.right;
				++cell_point.x )
			get_view_cell( object_pos.level, cell_point ).shadow_erase( id );
	}
}

// -------------------------------------------------------------------
// Compute the height of the specified object if placed at the
// specified location on the specified map.
// -------------------------------------------------------------------
int t_abstract_adventure_map::compute_height( t_abstract_adv_object const& object,
											  t_level_map_point_2d const&  pos ) const
{
	int height_sum = 0;
	int num_vertices = 0;

	t_footprint const & footprint = object.get_footprint();
	t_map_point_2d footprint_size = footprint.get_size();

	if ( footprint.are_any_cells_flat() )
	{
		static std::vector< bool > is_vertex_flat_vector;
		is_vertex_flat_vector.resize( ( footprint_size.row + 1 ) * ( footprint_size.column + 1 ) );
		std::fill( is_vertex_flat_vector.begin(), is_vertex_flat_vector.end(), false );

		std::vector< bool >::iterator is_vertex_flat_column_iter = is_vertex_flat_vector.begin();
		std::vector< bool >::iterator is_vertex_flat_iter;

		t_map_point_2d cell_point;
		for (	cell_point.column = 0;
				cell_point.column < footprint_size.column;
				++cell_point.column )
		{
			is_vertex_flat_iter = is_vertex_flat_column_iter;
			for (	cell_point.row = 0;
					cell_point.row < footprint_size.row;
					++cell_point.row )
			{
				if ( footprint.is_cell_flat( cell_point ) )
				{
					*is_vertex_flat_iter = true;
					*( is_vertex_flat_iter + 1 ) = true;
					*( is_vertex_flat_iter + footprint_size.row + 1 ) = true;
					*( is_vertex_flat_iter + footprint_size.row + 2 ) = true;
				}
				++is_vertex_flat_iter;
			}
			is_vertex_flat_column_iter += footprint_size.row + 1;
		}

		is_vertex_flat_iter = is_vertex_flat_vector.begin();
		t_map_point_2d vertex_point;
		for (	vertex_point.column = pos.column;
				vertex_point.column <= pos.column + footprint_size.column;
				++vertex_point.column )
		{
			for (	vertex_point.row = pos.row;
					vertex_point.row <= pos.row + footprint_size.row;
					++vertex_point.row )
			{
				if ( *is_vertex_flat_iter && is_vertex_valid( vertex_point ) )
				{
					++num_vertices;
					height_sum += get_tile_vertex( t_level_map_point_2d( vertex_point, pos.level ) ).get_height();
				}

				++is_vertex_flat_iter;
			}
		}
	}
	else
	{
		t_map_point_2d vertex_point;
		for (	vertex_point.column = pos.column;
				vertex_point.column <= pos.column + footprint_size.column;
				++vertex_point.column )
		{
			for (	vertex_point.row = pos.row;
					vertex_point.row <= pos.row + footprint_size.row;
					++vertex_point.row )
			{
				if ( is_vertex_valid( vertex_point ) )
				{
					++num_vertices;
					height_sum += get_tile_vertex( t_level_map_point_2d( vertex_point, pos.level ) ).get_height();
				}
			}
		}
	}

	if ( num_vertices == 0 )
		return 0;

	return ( height_sum + num_vertices / 2 ) / num_vertices;
}

// -------------------------------------------------------------------
// Free functions
// -------------------------------------------------------------------

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool is_under_fog_of_war(
	t_abstract_adventure_map const &	map,
	int									team_num,
	t_level_map_point_2d const &		object_pos,
	t_map_point_2d const &				footprint_size )
{
	return		team_num >= 0
			&&	is_under_fog_of_war_helper( map, team_num, object_pos, footprint_size, t_test_visible() );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool is_under_fog_of_war(
	t_abstract_adventure_map const &		map,
	int										team_num,
	t_abstract_adventure_map::t_object_id	object_id )
{
	if ( team_num < 0 )
		return false;

	t_level_map_point_2d object_pos = map.get_object_pos( object_id );
	t_map_point_2d footprint_size = map.get_object( object_id ).get_footprint().get_size();

	return is_under_fog_of_war_helper( map, team_num, object_pos, footprint_size, t_test_visible() );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool is_under_shroud(
	t_abstract_adventure_map const &	map,
	int									team_num,
	t_level_map_point_2d const &		object_pos,
	t_map_point_2d const &				footprint_size )
{
	return		team_num >= 0
			&&	is_under_fog_of_war_helper( map, team_num, object_pos, footprint_size, t_test_explored() );
}

// -------------------------------------------------------------------
// -------------------------------------------------------------------
bool is_under_shroud(
	t_abstract_adventure_map const &		map,
	int										team_num,
	t_abstract_adventure_map::t_object_id	object_id )
{
	if ( team_num < 0 )
		return false;

	t_level_map_point_2d object_pos = map.get_object_pos( object_id );
	t_map_point_2d footprint_size = map.get_object( object_id ).get_footprint().get_size();

	return is_under_fog_of_war_helper( map, team_num, object_pos, footprint_size, t_test_explored() );
}
